package com.dyz.leetcode._10_slidingWindow;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class _76_minWindow {


    public String minWindow(String s, String t) {

        //统计字符串t中每个字符出现的次数
        int[] cntT = new int[60];
        //统计t中不同的字符数
        int uniqueCharsInT = 0;
        for (char c:t.toCharArray()){
            if(cntT[c-'A']==0){uniqueCharsInT++;}
            cntT[c-'A']++;
        }
        int left = 0;
        int right = 0;
        //窗口中每个字符出现的次数
        int[] windowCnts = new int[60];
        // 记录当前窗口中字符出现的次数和 t 中字符出现次数相等的字符数
        int matchedChars = 0;
        int[] ans = {-1, 0, 0};
        while (right<s.length()){
            char rightChar = s.charAt(right);
            int rightCharIndex = rightChar-'A';
            windowCnts[rightCharIndex]++;
            if(windowCnts[rightCharIndex]==cntT[rightCharIndex]){
                matchedChars++;
            }
            while (left<=right && matchedChars==uniqueCharsInT){
                //找到了符合条件的子串
                if(ans[0]==-1){

                }
                // 尝试缩减窗口，因为我们想找到最短符合条件的子串
                if (ans[0] == -1 || right - left + 1 < ans[0]) {
                    ans[0] = right - left + 1;
                    ans[1] = left;
                    ans[2] = right;
                }

                char leftChar = s.charAt(left);
                int leftCharIndex = leftChar - 'A';
                windowCnts[leftCharIndex]--;
                if (windowCnts[leftCharIndex] < cntT[leftCharIndex]) {
                    matchedChars--;
                }
                left++;
            }


            right++;
        }
    return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }


}
